/*
 * @auther  yaoleilei<windowhero@sina.com>
 * @date    Fri Sep 22 20:45:49 CST 2017
 */
#ifndef __FULLMATCH_H__
#define __FULLMATCH_H__
#define _GNU_SOURCE
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include <pthread.h>
#include <time.h>
#include "list.h"

#if 1
#define FULLMATCH_LOG(fmt, ...)     printf("line %u: "fmt, __LINE__, ##__VA_ARGS__)
#define FULLMATCH_ERR(fmt, ...)     printf("line %u: "fmt, __LINE__, ##__VA_ARGS__)
#else
#define FULLMATCH_LOG(...)
#define FULLMATCH_ERR(fmt, ...)     printf("line %u: "fmt, __LINE__, ##__VA_ARGS__)
#endif

#define FULLMATCH_DEFAULT_CHAR_LIST "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789.%~!@#$&*()=:/,;?+'-_`|[]{}\\"
#define FULLMATCH_DEFAULT_CHAR_LIST_LEN (sizeof(FULLMATCH_DEFAULT_CHAR_LIST) - 1)

#define FULLMATCH_FULL_CHAR_LIST \
    "\x00\x01\x02\x03\x04\x05\x06\x07\x08\x09\x0a\x0b\x0c\x0d\x0e\x0f" \
    "\x10\x11\x12\x13\x14\x15\x16\x17\x18\x19\x1a\x1b\x1c\x1d\x1e\x1f" \
    "\x20\x21\x22\x23\x24\x25\x26\x27\x28\x29\x2a\x2b\x2c\x2d\x2e\x2f" \
    "\x30\x31\x32\x33\x34\x35\x36\x37\x38\x39\x3a\x3b\x3c\x3d\x3e\x3f" \
    "\x40\x41\x42\x43\x44\x45\x46\x47\x48\x49\x4a\x4b\x4c\x4d\x4e\x4f" \
    "\x50\x51\x52\x53\x54\x55\x56\x57\x58\x59\x5a\x5b\x5c\x5d\x5e\x5f" \
    "\x60\x61\x62\x63\x64\x65\x66\x67\x68\x69\x6a\x6b\x6c\x6d\x6e\x6f" \
    "\x70\x71\x72\x73\x74\x75\x76\x77\x78\x79\x7a\x7b\x7c\x7d\x7e\x7f" \
    "\x80\x81\x82\x83\x84\x85\x86\x87\x88\x89\x8a\x8b\x8c\x8d\x8e\x8f" \
    "\x90\x91\x92\x93\x94\x95\x96\x97\x98\x99\x9a\x9b\x9c\x9d\x9e\x9f" \
    "\xa0\xa1\xa2\xa3\xa4\xa5\xa6\xa7\xa8\xa9\xaa\xab\xac\xad\xae\xaf" \
    "\xb0\xb1\xb2\xb3\xb4\xb5\xb6\xb7\xb8\xb9\xba\xbb\xbc\xbd\xbe\xbf" \
    "\xc0\xc1\xc2\xc3\xc4\xc5\xc6\xc7\xc8\xc9\xca\xcb\xcc\xcd\xce\xcf" \
    "\xd0\xd1\xd2\xd3\xd4\xd5\xd6\xd7\xd8\xd9\xda\xdb\xdc\xdd\xde\xdf" \
    "\xe0\xe1\xe2\xe3\xe4\xe5\xe6\xe7\xe8\xe9\xea\xeb\xec\xed\xee\xef" \
    "\xf0\xf1\xf2\xf3\xf4\xf5\xf6\xf7\xf8\xf9\xfa\xfb\xfc\xfd\xfe\xff"
#define FULLMATCH_FULL_CHAR_LIST_LEN 256

typedef struct fullmatch_pattern {
    struct fullmatch_pattern *next;
    void                    *userdata;
} fullmatch_pattern_t;

typedef struct cpn0909 {
    uint8_t c;
    void *p;
    struct cpn0909 *n;
} cpn0909_t;

typedef struct {
#ifdef ENABLE_FULLMATCH_NODELIST
    struct list_head node;
#endif
    cpn0909_t *cpn;
    fullmatch_pattern_t *fullmatch_pattern;
} fullmatch_node_t;

typedef void (*FULLMATCH_USERFREE)(void *);

struct fullmatch {
    unsigned item_count;
    unsigned state_count; uint64_t state_mem;
    unsigned pattern_count; uint64_t pattern_mem;
    unsigned cpn_count;     uint64_t cpn_mem;
    struct list_head state_list;
    fullmatch_node_t        root_state;
    FULLMATCH_USERFREE       fullmatch_userfree;
};

static inline fullmatch_pattern_t *fullmatch_find(struct fullmatch *m, const unsigned char *path, int path_len,
        int match(struct fullmatch *m, fullmatch_pattern_t *fullmatch_pattern, const unsigned char *path, int path_len, int match_host_pos, int match_path_pos, void *context),
        void *context)
{
    fullmatch_node_t *node = &m->root_state;
    fullmatch_pattern_t *fullmatch_pattern;
    int i;
    for (i = 0; i < path_len; i++){
        unsigned char next_state_pos = path[i]; if (node->cpn == NULL) return NULL;
        cpn0909_t *tmp;
        for (tmp = node->cpn; tmp; tmp = tmp->n) {
            if (tmp->c == next_state_pos) break;
        }
        if (tmp == NULL) return NULL;
        node = tmp->p;
        if (node == NULL) return NULL;
    }
    for(fullmatch_pattern = node->fullmatch_pattern; fullmatch_pattern; fullmatch_pattern = fullmatch_pattern->next) {
        if (match == NULL) return fullmatch_pattern;
        if (match(m, fullmatch_pattern, path, path_len, 0, i, context) > 0) return fullmatch_pattern;
    }
    return NULL;
}

static inline int fullmatch_add_full_extra(struct fullmatch *m, const unsigned char *path, int path_len, void *userdata, int update)
{
    int i;

    if (update) {
        fullmatch_pattern_t *t = fullmatch_find(m, path, path_len, NULL, NULL);
        if (t) {
            if (t->userdata) { if (m->fullmatch_userfree) m->fullmatch_userfree(t->userdata); else free(t->userdata); }
            t->userdata = userdata;
            return 0;
        }
    }
    fullmatch_pattern_t *fullmatch_pattern = calloc(1, sizeof(fullmatch_pattern_t)); if (fullmatch_pattern == NULL) { FULLMATCH_ERR("fail to calloc\n"); return -1; } m->pattern_mem += sizeof(fullmatch_pattern_t); m->pattern_count++;
    fullmatch_pattern->userdata = userdata;

    fullmatch_node_t *node = &m->root_state;

    for (i = 0; i < path_len; i++) {
        unsigned char next_state_pos = path[i];
        cpn0909_t *tmp;
        for (tmp = node->cpn; tmp; tmp = tmp->n) {
            if (tmp->c == next_state_pos) break;
        }
        if (tmp == NULL) {
            tmp = calloc(1, sizeof(*tmp)); if (tmp == NULL) { FULLMATCH_ERR("error\n"); exit(1); } m->cpn_count++; m->cpn_mem += sizeof(cpn0909_t);
            tmp->p = calloc(1, sizeof(fullmatch_node_t)); if (tmp->p == NULL) { FULLMATCH_ERR("fail to calloc[%m]\n"); return -1; } m->state_count++; m->state_mem += sizeof(fullmatch_node_t);
            tmp->c = next_state_pos;
            tmp->n = node->cpn;
            node->cpn = tmp;
        }
        node = tmp->p;
    }
    fullmatch_pattern->next = node->fullmatch_pattern;
    node->fullmatch_pattern = fullmatch_pattern;
    m->item_count++;
    return 0;
}
static inline int fullmatch_add_full(struct fullmatch *m, const unsigned char *full, void *userdata)
{
    if (full == NULL) return -1;
    int full_len = strlen((const char *)full);
    const unsigned char *path = full;
    int path_len = full_len;

    return fullmatch_add_full_extra(m, path, path_len, userdata, 1);
}

static inline struct fullmatch *fullmatch_new(FULLMATCH_USERFREE fullmatch_userfree)
{
    struct fullmatch *m = calloc(1, sizeof(struct fullmatch)); if (m == NULL) { FULLMATCH_ERR("fail to calloc[%m]\n"); return NULL; }
    m->fullmatch_userfree = fullmatch_userfree;
    INIT_LIST_HEAD(&m->state_list);
    return m;
}

#ifdef ENABLE_FULLMATCH_NODELIST
static inline void fullmatch_free(struct fullmatch *m)
{
    if (m == NULL) return;

    fullmatch_node_t *node, *n;
    list_for_each_entry_safe(node, n, &m->state_list, node) {
        list_del(&node->node);

        fullmatch_pattern_t *fullmatch_pattern = node->fullmatch_pattern;
        while (fullmatch_pattern) {
            fullmatch_pattern_t *fullmatch_pattern_next = fullmatch_pattern->next;
            if (fullmatch_pattern->userdata) {
                if (m->fullmatch_userfree) m->fullmatch_userfree(fullmatch_pattern->userdata); else free(fullmatch_pattern->userdata);
            }
            free(fullmatch_pattern);
            fullmatch_pattern = fullmatch_pattern_next;
        }
        free(node);
    }
    free(m);
}
#endif

static inline void fullmatch_stat(struct fullmatch *m)
{
    LLOG("item_count %u\n", m->item_count);
    LLOG("pattern     size %3lu count %-10u mem %5"PRIu64"m %"PRIu64"\n", sizeof(fullmatch_pattern_t)       , m->pattern_count   , m->pattern_mem   /1000000, m->pattern_mem   );
    LLOG("node        size %3lu count %-10u mem %5"PRIu64"m %"PRIu64"\n", sizeof(fullmatch_node_t)         , m->state_count     , m->state_mem     /1000000, m->state_mem     );
    LLOG("cpn         size %3lu count %-10u mem %5"PRIu64"m %"PRIu64"\n", sizeof(cpn0909_t)                 , m->cpn_count       , m->cpn_mem       /1000000, m->cpn_mem       );
}

#endif
